#!/usr/bin/python
#
# Copyright (c) 2008, Google Inc.
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
#
#     * Redistributions of source code must retain the above copyright
# notice, this list of conditions and the following disclaimer.
#     * Redistributions in binary form must reproduce the above
# copyright notice, this list of conditions and the following disclaimer
# in the documentation and/or other materials provided with the
# distribution.
#     * Neither the name of Google Inc. nor the names of its
# contributors may be used to endorse or promote products derived from
# this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

# ---
# Author: Filipe Almeida
#
# Generate a C include file from a finite state machine definition.
#
# Right now the form is the one expected by htmlparser.cc so this file is pretty
# tightly coupled with htmlparser.cc.
#

__author__ = 'opensource@google.com (Filipe Almeida)'

import sys
import getopt

TABSTOP = 2

class FSMGenerator(object):

  sm = {}  # dictionary that contains the finite state machine definition
           # loaded from a config file.
  states = {}  # Mapping between the state name and it's definition.
  state_list = []  # Ordered list of state names.
  transitions = []  # List of transitions.
  conditions = {}  # Mapping between the condition name and the bracket
                   # expression.


  def state(self, **dict):
    """ Called from the definition file with the description of the state.

    Receives a dictionary and populates internal structures based on it. The
    dictionary is in the following format:

    {'name': state_name,
     'external': exposed state name,
     'transitions': [
       [condition, destination_state ],
       [condition, destination_state ]
     ]
    }

    """

    name = dict['name']
    external = dict['external']
    self.state_list.append(name)
    self.states[name] = dict

    for (condition, destination) in dict['transitions']:
      transition = {'condition': condition,
                    'src': name,
                    'dst': destination }
      self.transitions.append(transition)

  def condition(self, name, expression):
    """ Called from the definition file with the definition of a condition.

    Receives the name of the condition and it's expression.
    """
    self.conditions[name] = expression

  def prefix(self):
    """ return a c declaration prefix """

    return self.sm['name'].lower() + '_'

  def c_state_internal(self, st):
    """ return the internal name of the state """

    return "%sSTATE_INT_%s" % (self.prefix().upper(), st.upper())

  def c_state_external(self, st):
    """ return the external name of the state """

    return "%sSTATE_%s" % (self.prefix().upper(), st.upper())

  def tab(self):
    """ Returns an expanded tab string """
    return "\t".expandtabs(TABSTOP)

  def make_tuple(self, data):
    """ converts data to a string representation of a c tuple to be inserted
    into a list.
    """

    return "%s{ %s }" % (self.tab(), ', '.join(data))

  def print_header(self):
    """ Print the include file header """

    if 'comment' in self.sm:
      print "/* " + self.sm['comment']
    else:
      print "/* State machine definition for " + self.sm['name']
    print " * Auto generated by generate_fsm.py. Please do not edit."
    print " */"
    print

  def print_enum(self, name, data):
    """ Print a c enum definition """
    list = []  # output list

    print "enum %s {" % name

    for e in data:
      list.append(self.tab() + e)
    print ",\n".join(list) + "\n};\n"


  def print_struct_list(self, name, type, data):
    """ Print a c flat list.

    Generic function to print list in c in the form of a struct.

    Args:
      name: name of the structure.
      type: type of the struct.
      data: contents of the struct as a list of elements
    """
    list = []  # output list

    print "static const %s %s[] = {" % (type, name)

    for e in data:
      list.append(self.tab() + e)
    print ",\n".join(list)
    print "};\n"


  def print_struct_list2(self, name, type, data):
    """ Print a c list of lists.
 
    Generic function to print a list of lists in c in the form of a struct.

    Args:
      name: name of the structure.
      type: type of the struct.
      data: contents of the struct as a list of lists.
    """
    list = []  # output list

    print "static const %s %s[] = {" % (type, name)

    for e in data:
      list.append(self.make_tuple(e))
    print ",\n".join(list)
    print "};\n"


  def print_states_enum(self):
    """ Print the internal states enum

    Prints an enum containing all the valid states.
    """
    list = []  # output list

    for state in self.state_list:
      list.append(self.c_state_internal(state))
    self.print_enum(self.prefix() + 'state_internal_enum', list)


  def print_states_external(self):
    """ Print a struct with a mapping from internal to external states """
    list = []  # output list

    for state_name in self.state_list:
      list.append(self.c_state_external(self.states[state_name]['external']))

    self.print_struct_list(self.prefix() + 'states_external', 'int', list)

  def print_transitions(self):
    """ Print the state transition list.

    Prints a structure that fills the following struct definition based on a
    list of (condition, source, destination) tuples stored in a variable named
    transitions:

    struct statetable_transitions_s {
      const char *condition;
      state source;
      state destination;
    };

    The conditions are mapped from the conditions variable.
    The resulting list is reversed as htmlparser.c expectes the list in
    reversed order of execution, and an terminator is added:

    { NULL, STATEMACHINE_ERROR, STATEMACHINE_ERROR }
    """
    list = []          # output list

    for transition in self.transitions:
      (condition, src, dst) = (transition['condition'],
                               transition['src'],
                               transition['dst'])
      new_condition = '"%s"' % self.conditions[condition]
      list.append([new_condition,
                   self.c_state_internal(src),
                   self.c_state_internal(dst)
                   ])

    list.reverse() # The include appears in reversed order
    list.append(['NULL', 'STATEMACHINE_ERROR', 'STATEMACHINE_ERROR'])

    self.print_struct_list2(self.prefix() + 'state_transitions',
                            'struct statetable_transitions_s', list)

  def load(self, filename):
    """ Load the state machine definition file.

    In the definition file, which is based on the python syntax, the following
    variables and functions are defined.

    name: Name of the state machine
    comment: Comment line on the generated file.
    condition(): A mapping between condition names and bracket expressions.
    state(): Defines a state and it's transitions. It accepts the following
             attributes:
      name: name of the state
      external: exported name of the state. The exported name can be used
                multiple times in order to create a super state.
      transitions: List of pairs containing the condition for the transition
                   and the destination state. Transitions are ordered so if
                   a default rule is used, it must be the last one in the list.

    Example:

    name = 'c comment parser'

    condition('/', '/')
    condition('*', '*')
    condition('linefeed', '\\n')
    condition('default', '[:default:]')

    state(name = 'text',
          external = 'comment',
          transitions = [
            [ '/', 'comment_start' ],
            [ 'default', 'text' ]
          ])

    state(name = 'comment_start',
          external = 'comment',
          transitions = [
            [ '/', 'comment_line' ],
            [ '*', 'comment_multiline' ],
            [ 'default', 'text' ]
          ])

    state(name = 'comment_line',
          external = 'comment',
          transitions = [
            [ 'linefeed', 'text' ],
            [ 'default', 'comment_line' ]
          ])

    state(name = 'comment_multiline',
          external = 'comment',
          transitions = [
            [ '*', 'comment_multiline_close' ],
            [ 'default', 'comment_multiline' ]
          ])

    state(name = 'comment_multiline',
          external = 'comment',
          transitions = [
            [ '*', 'comment_multiline_close' ],
            [ 'default', 'comment_multiline' ]
          ])

    state(name = 'comment_multiline_close',
          external = 'comment',
          transitions = [
            [ '/', 'text' ],
            [ 'default', 'comment_multiline' ]
          ])

    """

    self.sm['state'] = self.state
    self.sm['condition'] = self.condition
    execfile(filename, self.sm)



  def print_num_states(self):
    """ Print a Macro defining the number of states. """

    print "#define %s_NUM_STATES %s\n" % (self.sm['name'].upper(),
                                          str(len(self.state_list) + 1))

  def generate(self):
    self.print_header()
    self.print_num_states()
    self.print_states_enum()
    self.print_states_external()
    self.print_transitions()

  def __init__(filename):
    pass

def main():

  gen = FSMGenerator()
  if len(sys.argv) != 2:
    print "usage: generate_fsm.py config_file"
    sys.exit(1)

  gen.load(sys.argv[1])
  gen.generate()


if __name__ == "__main__":
    main()
